//https://leetcode.cn/problems/lexicographically-smallest-beautiful-string/description/?envType=daily-question&envId=2024-06-22

void fun(string& s, int k) {
    if (s.size() == 0) {
        return;
    }
    int size = s.size();
    char c = s[size - 1];
    s.pop_back();
    char tmp1 = 0, tmp2 = 0;
    if (size >= 2)
        tmp1 = s[size - 2];
    if (size >= 3)
        tmp2 = s[size - 3];
    for (int i = 1; i <= 3; i++) {
        if (tmp1 != c + i && tmp2 != c + i && c + i < k + 'a') {
            s.push_back(c + i);
            return;
        }
    }
    fun(s, k);
    return;
}
class Solution {
public:
    string smallestBeautifulString(string s, int k) {
        int oldsize = s.size();
        fun(s, k);
        int size = s.size();
        if(size == 0)   return s;
        while (size < oldsize) {
            char tmp1 = 0, tmp2 = 0;
            if (size >= 1)
                tmp1 = s[size - 1];
            if (size >= 2)
                tmp2 = s[size - 2];
            cout<<tmp1<<' '<<tmp2<<endl;
            if (tmp1 != 'a' && tmp2 != 'a')
                s.push_back('a');
            else if (tmp1 != 'b' && tmp2 != 'b')
                s.push_back('b');
            else if (tmp1 != 'c' && tmp2 != 'c')
                s.push_back('c');
                size++;
        }
        return s;
    }
};